#include "main/utils.h"
#include "lib/list.h"
using namespace std;

class Solution {
  public:
    ListNode *detectCycle(ListNode *head) {
      if (!head)
        return nullptr;

      auto slow = head;
      auto fast = head;
      while (fast) {
        slow = slow->next;
        fast = fast->next;
        if (!fast) {
          return nullptr;
        }
        fast = fast->next;
        if (!fast) {
          return nullptr;
        }
        if (slow == fast) {
          break;
        }
      }
      int n = 1;
      fast = fast->next;
      while (slow != fast) {
        fast = fast->next;
        ++n;
      }
      slow = head;
      fast = head;
      for (int i = 0; i < n; ++i) {
        fast = fast->next;
      }
      while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
      }
      return fast;
    }

    ListNode *detectCycle1(ListNode *head) {
      unordered_set<ListNode*> st;
      auto node = head;
      while (node) {
        if (st.count(node)) {
          return node;
        }
        st.insert(node);
        node = node->next;
      }
      return nullptr;
    }

    ListNode *detectCycle2(ListNode *head) {
      if (!head || !head->next) {
        return nullptr;
      }
      auto slow = head->next;
      auto fast = head->next->next;
      while (slow != fast) {
        if (!fast || !fast->next) {
          return nullptr;
        }
        slow = slow->next;
        fast = fast->next->next;
      }
      slow = head;
      while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
      }
      return slow;
    }
};

int main() {
  ListNode* p1 = new ListNode();
  p1->value = 3;
  ListNode* p2 = new ListNode();
  p2->value = 2;
  ListNode* p3 = new ListNode();
  p3->value = 0;
  ListNode* p4 = new ListNode();
  p4->value = 4;

  ConnectNode(p1, p2);
  ConnectNode(p2, p3);
  ConnectNode(p3, p4);
  ConnectNode(p4, p2);

  Solution su;
  cout << su.detectCycle(p1)->value << endl;
  cout << su.detectCycle1(p1)->value << endl;
  cout << su.detectCycle2(p1)->value << endl;
}
